package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code36
 * @Description 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 * 示例 1：
 *
 * 输入: [1,6,3,2,5]
 * 输出: false
 * 示例 2：
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 * 提示：
 *
 * 数组长度 <= 1000
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-19 20:58
 */
public class Code36 {
    public static void main(String[] args) {
        int[] arr = {7, 4, 6, 5};
        System.out.println(verifyPostorder(arr));
    }

    public static boolean verifyPostorder(int[] postorder) {
        if (postorder.length == 0) {
            return true;
        }
        return check(postorder, 0, postorder.length - 1);
    }

    public static boolean check(int[] arr, int low, int high) {

        if (low + 1 >= high) {
            return true;
        }

        int temp = arr[high]; // 取出根节点的值
        int pivot = low; // pivot为左右子树的分界线

        while (arr[pivot] < temp) {
            pivot++; // 找到第一个大于根节点的结点
        }

        /*
        特殊情况1，如果没有一个结点大于根节点的值的话那么所有的结点都是根节点的左子节点，递归的判断左子树
         */
        if (pivot == high) {
            return check(arr, low, high - 1);
        }

        /*
        如果找到了一个大于根节点的结点，那么正确的情况是从pivot 到 high - 1结点的值都是根节点的右节点也就是都大于根节点
         */
        for (int i = pivot; i < high; i++) {
            if (arr[i] < temp) {
                return false; // 如果出现一个小于的则返回false
            }
        }
        /*
        特殊情况2，如果所有的结点都大于根节点，那么所有结点都是根节点的右子节点，递归的判断右子树
         */
        if (pivot == low) {
            return check(arr, pivot, high - 1);
        }
        /*
        一般情况，既有左子树，又有右子树
         */
        return check(arr, low, pivot - 1) && check(arr, pivot, high - 1);
    }
}
/*
关于树的遍历大致思路就是对序列的划分，判断哪个结点是根节点
哪个结点是根节点的左子树结点，哪些是右子树结点
而对于二叉搜索树有个特点就是根节点的值小于右节点而大于左节点
所以给定一个二叉搜索树的后序遍历序列，他的序列划分一定是
左子树  右子树  根
并且满足 左子树 < 根 < 右子树
并且他的左右子树也都分别递归的满足以上两个条件
所以难点就在于如何确定哪些结点是左子树，哪些结点是右子树，即找到左右子树的边界
而确定根节点是简单的，一定在末尾
 */